package org.xqh.study.leetcode.algorithm.studyplan;

/**
 * @ClassName Trie
 * @Description TODO
 * @Author xuqianghui
 * @Date 2021/3/4 20:29
 * @Version 1.0
 */
public class Trie {

    private final static int R = 26;//26个 小写 字母

    TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;//初始化 从 根节点 查询
        int len = word.length();
        for(int i = 0; i < len; i ++){
            char cur = word.charAt(i);
            if(node.containsKey(cur)){
                node = node.get(cur);
            }else {
                node.put(cur, new TrieNode());
                node = node.get(cur);
            }
        }
        node.setEnd();//标识 为 末端节点.
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = wrapperSearch(word);
        if(null != node){
            return node.getEnd();
        }
        return false;
    }

    public TrieNode wrapperSearch(String word){
        TrieNode node = root;
        int len = word.length();
        boolean ret = true;
        for(int i = 0; i < len; i ++){
            char cur = word.charAt(i);
            if(!node.containsKey(cur)){
                ret = false;
                break;
            }
            node = node.get(cur);
        }
        if(ret){
            return node;
        }

        return null;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return wrapperSearch(prefix) != null;
    }


    /**
     * 前缀树节点对象
     */
    public static class TrieNode{

        private TrieNode[] links;//链接节点

        private boolean isEnd;

        public TrieNode(){
            links = new TrieNode[R];
        }

        public void put(char ch, TrieNode node){
            links[ch - 'a'] = node;
        }

        public TrieNode get(char ch){
            return links[ch - 'a'];
        }

        public boolean containsKey(char ch){
            return links[ch - 'a'] != null;
        }

        public void setEnd(){
            isEnd = true;
        }


        public void setEnd(boolean isEnd){
            this.isEnd = isEnd;
        }

        public boolean getEnd(){
            return isEnd;
        }

    }

    public static void main(String[] args) {
        String str = "abc";
        f(str);
        System.out.println(str);
    }

    public static String f(String str){
        str = "aof";
        return str;
    }
}
